#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define R(i,j) r[(i-1)*t+j-1]
#define F1(i) f1[i-1]
#define F2(i) f2[i-1]
#define S(i,j) s[(i-1)*t+j-1]
#define P(i,j) p[(i-1)*t+j-1]
int main()
{
	int i,j,k,l,temp,temp1;
	int m,n,t,mv,mp;
	int *r,*f1,*f2,*s,*p;
	scanf("%d %d %d",&m,&n,&t);
	r=(int *)malloc(n*t*sizeof(int));
	f1=(int *)malloc(n*sizeof(int));
	f2=(int *)malloc(n*sizeof(int));
	s=(int *)malloc(n*t*sizeof(int));
	p=(int *)malloc(n*t*sizeof(int));
	for(i=1;i<=n;i++) for(j=1;j<=t;j++) scanf("%d",&R(i,j));
	for(i=1;i<=n;i++) scanf("%d %d",&F1(i),&F2(i));
	for(i=1;i<=n;i++) S(i,1)=R(i,1)*m,P(i,1)=0;
	for(i=2;i<=t;i++)
	{
		mv=0;
		mp=0;
		for(j=1;j<=n;j++)
		{
			temp=S(j,i-1)-F2(j);
			if(temp>mv) mv=temp,mp=j;
		}
		for(j=1;j<=n;j++)
		{
			temp=S(mp,i-1)-F2(mp);
			temp1=S(j,i-1)-F1(j);
			if(temp>temp1)
			{
				S(j,i)=temp;
				P(j,i)=mp;
			}
			else
			{
				S(j,i)=temp1;
				P(j,i)=j;
			}
		}
	}
	mv=0;
	for(i=1;i<n;i++)
	{
		temp=S(i,t);
		if(temp>mv) mv=temp,mp=i;
	}
	printf("max amount after %d year is %d, and is in inv_bank %d\n",t,mv,mp);
	free(r);
	free(f1);
	free(f2);
	free(s);
	free(p);
	return 0;
}




